今天來解YKL33(UVA299)：Train Swapping

Train Swapping

目的將序列排序
計算交換的次數

這裡我們用Bubble Sort

BubbleSort(A):
    n = length(A)
    for i = 0 to n - 1 do:
        swapped = false
        for j = 0 to n - i - 2 do:
            if A[j] > A[j + 1] then:
                // 交换相鄰的元素
                swap(A[j], A[j + 1])
                swapped = true
        
        if swapped == false then:
            break

#include <iostream>

using namespace std;

int main(){
    int cases;
    cin >> cases;
    while(cases--){
        int n;
        cin >> n;
        cin.ignore();
        int arr[n];
        for(int i=0;i<n;i++){
            int nums=0;
            cin >> nums;
            arr[i] = nums;
        }
        
        int count = 0;
        for(int i = 0; i < n; i++){
            bool swapped = false;
            for(int j = 0; j < n; j++){
                if(arr[j] > arr[j + 1]){
                    swapped = true;
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                    count++;
                }
            }
            if(swapped == false) break;
        }
        cout << "Optimal train swapping takes " << count << " swaps." << endl;
    }
    return 0;
}